load "wgraph.rb"

def make_sample_graph
$g = WGraph.new
v = [Vertex.new(0)]
for i in 1..12
  v << Vertex.new(i)
end

for i in 1..12
  $g.add_vertex(v[i])
end

$g.add_edge(v[1], v[2], 1)
$g.add_edge(v[1], v[11], 1)
$g.add_edge(v[1], v[7], 1)

$g.add_edge(v[2], v[3], 1)
$g.add_edge(v[2], v[11], 1)

$g.add_edge(v[3], v[10], 1)
$g.add_edge(v[3], v[4], 1)

$g.add_edge(v[4], v[5], 1)
$g.add_edge(v[4], v[9], 1)

$g.add_edge(v[5], v[6], 1)
$g.add_edge(v[5], v[9], 1)

$g.add_edge(v[6], v[7], 1)
$g.add_edge(v[6], v[8], 1)

$g.add_edge(v[7], v[8], 1)

$g.add_edge(v[8], v[12], 1)

$g.add_edge(v[9], v[12], 1)

$g.add_edge(v[10], v[11], 1)
$g.add_edge(v[10], v[12], 1)
end

#------------------------------------------

def delete_neighbours(vertices, v)
  v.adjList.each { |w|
    vertices.delete(w)
  }
end


def procedure1(vertices, s)
  puts "procedure1"
  
  return s if vertices.empty?
  
  max = -1
  v_max_index = -1
  
  i=0
  vertices.each { |v|
    num_adjoinable_vertices = vertices.size - (vertices & v.adjList).size - 1
    
    puts "v = #{v}, rho= #{num_adjoinable_vertices}"
    
    if num_adjoinable_vertices > max
      max = num_adjoinable_vertices
      v_max_index = i
    end
    
    i+=1
  }
  
  
  puts "v_max= #{vertices[v_max_index]}, rho= #{max}"
  puts ""
  
  v = vertices[v_max_index]
  s << v
  vertices.delete_at(v_max_index)
  v.adjList.each { |w|
    vertices.delete(w)
  }
  
  puts "s #{s}"
  puts "vertices #{vertices}"
  
  return procedure1(vertices, s)
  
  
end




def procedure2(vertices, s)
  puts
  puts "s #{s}"
  puts "vertices #{vertices}"
  puts "procedure2"
  puts
  
  
  #s_vw = s.clone
  x = nil
  w = nil
  
  vertices.each { |v|
    w = v.adjList & s
    if w.size == 1
      x = w[0]
      s.delete(x)
      s << v
      
      puts "swap #{x} for #{v}"
      puts
      
      break;
    end
  }
  
  vertices.delete(x)
  vertices |= w
  
  puts "s #{s}"
  puts "vertices #{vertices}"
  
  s.each { |y|
    delete_neighbours(vertices, y)
    vertices.delete(y)
  }
  return procedure1(vertices, s)
end



def procedure3(k)
  
  maximal_independent_sets = []
  
  #PART 1
  $g.vertices.each { |v|
    
    s = [v]
    
    #-- calling of procedure 1 --
    vertices1 = $g.vertices.clone
    delete_neighbours(vertices1, v)
    vertices1.delete(v)
    puts
    puts "s #{s}"
    puts "vertices #{vertices1}"
    s = procedure1(vertices1, s)
    #base case
    if s.size >= k
      maximal_independent_sets << s
      k = s.size if s.size > k
      next
    end
    #-- calling of procedure 1 end --
  
    #-- calling of procedure 2 --
    k.times {
      vertices2 = $g.vertices.clone
      s.each { |w|
        vertices2.delete(w)
      }
      s = procedure2(vertices2, s)  
    }
    #base case
    if s.size >= k
      maximal_independent_sets << s
      k = s.size if s.size > k
      next
    end
    #-- calling of procedure 2 end --
    
  }
  
  #PART 2
  n = maximal_independent_sets.size
  for i in 0..n-1
    s_i = maximal_independent_sets[i]
    
    for j in 0..n-1
      s_j = maximal_independent_sets[j]
      next if s_i == s_j
      
      s = s_i & s_j
      
      #-- calling of procedure 1 --
      vertices1 = $g.vertices.clone
      s.each { |v|
        delete_neighbours(vertices1, v)
        vertices1.delete(v)
      }
      s = procedure1(vertices1, s)
      #base case
      if s.size >= k
        maximal_independent_sets << s
        k = s.size if s.size > k
        next
      end
      #-- calling of procedure 1 end --
    
      #-- calling of procedure 2 --
      k.times {
        vertices2 = $g.vertices.clone
        s.each { |w|
          vertices2.delete(w)
        }
        s = procedure2(vertices2, s)  
      }
      #base case
      if s.size >= k
        maximal_independent_sets << s
        k = s.size if s.size > k
        next
      end
      #-- calling of procedure 2 end --
        
    end
    
  end
  
  return maximal_independent_sets
  
end


def compute_sufficient_size_for_maximum_independent_set(g)
  n = g.count_v
  
  max_degree = 0
  g.vertices.each { |v|
    
      #get degree of v (i.e. num of neighbours)
      degree = v.adjList.size
      max_degree = degree if degree > max_degree
  }
  
  #compute sufficient size for maximum independent set
  sufficient_size = ( n / (max_degree+1.0) ).ceil
  
  puts
  puts "n=#{n}, max_degree=#{max_degree}, k=#{sufficient_size}"
  
  return sufficient_size
end



# Shorten Actor Names
def shorten_actor_names
  $g.vertices.each { |v|
    v.value = v.value[0]
  }
end

shorten_actor_names

k = compute_sufficient_size_for_maximum_independent_set($g)

res = procedure3(k)

puts
p res
p res.size
puts

ans = nil
max = 0
for i in 0..res.size-1
  e = res[i]
  if e.size > max
    ans = e
    max = e.size
  end
end

p "final answer:"
p ans


